package algorithms

import (
	"Algorithms/util"
	"math"
	"sort"
)

//动态规划，如果一个问题包含其子问题的最优解，我们称它具有最优子结构性质
//两个最优解子问题必须是无关的才行，资源不能共享
//分治每一步都产生新问题 ，而动态规划是反复求解相同问题，把每次重叠问题存入内存即可

//锯钢条问题
//长度	1	2	3	4	5	6	7	8	9	10
//价格	1	5	8	9	10	17	17	20	24	30
//BenchmarkCutRod-8         112447              9048 ns/op
//BenchmarkCutRodTopToBottom-8     1639650               689 ns/op
//BenchmarkCutRodBottomToTop-8     1957590               598 ns/op

//递归算法
func CutRod(p []int, n int) int {
	if n == 0 {
		return 0
	}
	q := util.INT_MIN
	for i := 1; i <= n; i++ {
		//i代表前一段长度，p[i-1]即该长度的价格，递归子式代表后一段价格
		q = util.CompareMax(CutRod(p, n-i)+p[i-1], q)
	}
	return q
}

//自上而下的动态规划,需要带备忘
func CutRodTopToBottom(p []int, n int) int {
	if n == 0 {
		return 0
	}
	//创建备忘录，索引代表该长度下最大价格
	r := make([]int, n+1)
	for i := 0; i < n; i++ {
		r[i] = -1 //给r初始化，都是负数
	}
	return memorizedTopToBottom(p, r, n)
}

func memorizedTopToBottom(p, r []int, n int) int {
	//如果r中存了最大值，就不用走下面的递归了
	if r[n] > 0 {
		return r[n] //如果r值是正数，说明已经求过该条件下最优解了，就不用继续递归直接返回就好
	}
	var q int
	if n == 0 {
		q = 0 //终止条件n=0无法在进行切割
	} else {
		q = util.INT_MIN
		for i := 1; i <= n; i++ {
			q = util.CompareMax(memorizedTopToBottom(p, r, n-i)+p[i-1], q)
		}
	}
	//记录该长度最优解
	r[n] = q
	return q
}

//自底向上
func CutRodBottomToTop(p []int, n int) int {
	//自底向上的话更为简单，直接从小到大记录，最优解为前一个最优解加上这个
	r := make([]int, n+1)
	r[0] = 0
	//代表长度从1~n的钢条
	for i := 1; i <= n; i++ {
		q := -1
		//分离出一截和另一个子问题，记录所有里面最大值为q
		for j := 1; j <= i; j++ {
			q = util.CompareMax(q, r[i-j]+p[j-1])
		}
		r[i] = q
	}
	return r[n]
}

func LCSLength(x, y []string) int {
	var c = make([][]int, len(x))
	for i := 0; i < len(x); i++ {
		c[i] = make([]int, len(y))
	}

	for i := 0; i < len(x); i++ {
		for j := 0; j < len(y); j++ {
			if x[i] == y[j] {
				if i == 0 || j == 0 {
					c[i][j] = 0 + 1
				} else {
					c[i][j] = c[i-1][j-1] + 1
				}
			} else {
				m := i - 1
				n := j - 1
				if m < 0 {
					m = 0
				}
				if n < 0 {
					n = 0
				}
				c[i][j] = int(math.Max(float64(c[m][j]), float64(c[i][n])))
			}
		}
	}
	return c[len(x)-1][len(y)-1]
}

//对0-1背包问题回溯的第一步优化，添加一个矩阵剪枝,返回能装的最大值
//贪心——每次捡最小重量
//回溯——每个物品都装/不装试一遍
func FBacktracking(weight []int, w int) int {
	max := -1
	n := len(weight)
	var f func(i, cw int)
	f = func(i, cw int) {
		if i == n || cw == w { //物品用完或者装满了
			if cw > max {
				max = cw
			}
			return
		}
		f(i+1, cw) //不装
		if cw+weight[i] <= w {
			f(i+1, cw+weight[i]) //装
		}
	}
	f(0, 0)
	return max
}

//动态规划
func FDynamic(weight []int, w int) int {
	visited := make([][]bool, len(weight)+1)
	for i := range visited {
		visited[i] = make([]bool, w)
	}
	max := -1
	n := len(weight)
	var f func(i, cw int)
	f = func(i, cw int) {
		if i == n || cw == w { //物品用完或者装满了
			if cw > max {
				max = cw
			}
			return
		}
		if visited[i][cw] { //重复状态，这里优化了
			return
		}
		visited[i][cw] = true
		f(i+1, cw) //不装
		if cw+weight[i] <= w {
			f(i+1, cw+weight[i]) //装
		}
	}
	f(0, 0)
	return max
}

//非递归实现
func FDynamic2(weight []int, w int) int {
	visited := make([][]bool, len(weight))
	for i := range visited {
		visited[i] = make([]bool, w+1)
	}
	//初始化
	visited[0][0] = true
	if weight[0] < w {
		visited[0][weight[0]] = true
	}
	for i := 1; i < len(weight); i++ {
		for j := 0; j < w; j++ { //不装
			if visited[i-1][j] {
				visited[i][j] = true
			}
		}
		for j := 0; j <= w-weight[i]; j++ { //装
			if visited[i-1][j] {
				visited[i][j+weight[i]] = true
			}
		}
	}
	//找最大
	for i := w; i >= 0; i-- {
		if visited[len(weight)-1][i] {
			return i
		}
	}
	return 0
}

//非递归+一维数组
func FDynamic3(weight []int, w int) int {
	states := make([]bool, w+1)
	//初始化
	states[0] = true
	if weight[0] < w {
		states[weight[0]] = true
	}
	for i := 1; i < len(weight); i++ {
		//注意这里需要倒序遍历，防止本次循环影响之后的循环
		for j := w - weight[i]; j >= 0; j-- {
			if states[j] {
				//第i个放（不放的可能性已经在j上了
				states[j+weight[i]] = true
			}
		}
	}
	//找最大
	for i := w; i >= 0; i-- {
		if states[i] {
			return i
		}
	}
	return 0
}

//背包问题进化，+价格
func FValueDynamic(weight, value []int, w int) int {
	states := make([][]int, len(weight))
	for i := range states {
		states[i] = make([]int, w+1)
		for j := range states[i] {
			states[i][j] = -1
		}
	}
	//起始条件
	states[0][0] = 0
	states[0][weight[0]] = value[0]
	for i := 1; i < len(weight); i++ {
		for j := 0; j <= w; j++ { //不装第i个
			if states[i-1][j] >= 0 {
				states[i][j] = states[i-1][j]
			}
		}
		for j := 0; j <= w-weight[i]; j++ {
			if states[i-1][j] >= 0 {
				v := states[i-1][j] + value[i]
				if v > states[i][j+weight[i]] {
					states[i][j+weight[i]] = v
				}
			}
		}
	}
	maxvalue := -1
	for j := 0; j <= w; j++ {
		if states[len(weight)-1][j] > maxvalue {
			maxvalue = states[len(weight)-1][j]
		}
	}
	return maxvalue
}

//寻找最小路径，动态规划，从(0,0)到(n-1,n-1)，状态转移方程
func minDistDPState(w [][]int) int {
	m := len(w)
	n := len(w[0])
	states := make([][]int, m)
	for i := range states {
		states[i] = make([]int, n)
	}
	//初始化第一行列
	sum := 0
	for i := 0; i < m; i++ {
		sum += w[i][0]
		states[i][0] = sum
	}
	sum = 0
	for j := 0; j < n; j++ {
		sum += w[0][j]
		states[0][j] = sum
	}
	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			//从左或者从上面来谁短走哪
			states[i][j] = min(states[i-1][j], states[i][j-1]) + w[i][j]
		}
	}
	return states[m-1][n-1]
}

//64. 最小路径和 同上，递归+备忘录
func minDistDPMem(w [][]int) int {
	m := len(w)
	n := len(w[0])
	mem := make([][]int, m)
	for i := range mem {
		mem[i] = make([]int, n)
	}
	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	var f func(i, j int) int
	f = func(i, j int) int {
		if i == m-1 && j == n-1 {
			return w[i][j]
		}
		//备忘录里面有的
		if mem[i][j] > 0 {
			return mem[i][j]
		}
		minRight := math.MaxInt8
		if i < m-1 {
			minRight = f(i+1, j)
		}
		minDown := math.MaxInt8
		if j < n-1 {
			minDown = f(i, j+1)
		}
		currMinDIst := w[i][j] + min(minRight, minDown)
		mem[i][j] = currMinDIst
		return currMinDIst
	}
	return f(0, 0)
}

//莱文斯坦距离
func lwstDP(a, b string) int {
	m, n := len(a), len(b)
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	if a[0] == b[0] {
		dp[0][0] = 0
	} else {
		dp[0][0] = 1
	}
	//初始化
	for i := 1; i < m; i++ {
		//如果相等，把之前的都算不匹配，所以有lwst=i
		if a[i] == b[0] {
			dp[i][0] = i
		} else {
			dp[i][0] = dp[i-1][0] + 1
		}
	}
	for j := 1; j < n; j++ {
		if a[0] == b[j] {
			dp[0][j] = j
		} else {
			dp[0][j] = dp[0][j-1] + 1
		}
	}
	//工具函数
	min := func(a, b, c int) int {
		if a > b {
			if b > c {
				return c
			}
			return b
		} else {
			if a > c {
				return c
			}
			return a
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if a[i] == b[j] {
				dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, dp[i][j-1]+1)
			} else {
				//变1位----a删一位或者b添加一位------前面反之
				dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)
			}
		}
	}
	return dp[m-1][n-1]
}

//300. 最长递增子序列
func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	dp := make([]int, len(nums))
	dp[0] = 1
	max := 1
	for i := 1; i < len(dp); i++ {
		dp[i] = 1
		for j := i - 1; j >= 0; j-- {
			if nums[i] > nums[j] && dp[i] < dp[j]+1 {
				dp[i] = dp[j] + 1
			}
		}
		if dp[i] > max {
			max = dp[i]
		}
	}
	return max
}

//1220. 统计元音字母序列的数目,广度遍历
func countVowelPermutation(n int) int {
	dp := make([][5]int, n)
	mod := int(1e9 + 7)
	for i := 0; i < 5; i++ {
		dp[0][i] = 1
	}
	for i := 1; i < n; i++ {
		dp[i][0] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][4]) % mod
		dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % mod
		dp[i][2] = (dp[i-1][1] + dp[i-1][3]) % mod
		dp[i][3] = (dp[i-1][2]) % mod
		dp[i][4] = (dp[i-1][2] + dp[i-1][3]) % mod
	}
	return (dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + dp[n-1][3] + dp[n-1][4]) % mod
}

//118. 杨辉三角
func generate(numRows int) [][]int {
	res := make([][]int, numRows)
	for i := 0; i < numRows; i++ {
		res[i] = make([]int, i+1)
		for j := 0; j <= i; j++ {
			if j == 0 || j == i {
				res[i][j] = 1
			} else {
				res[i][j] = res[i-1][j] + res[i-1][j-1]
			}
		}
	}
	return res
}

//119. 杨辉三角 II
func getRow(rowIndex int) []int {
	res := make([][]int, rowIndex+1)
	for i := 0; i <= rowIndex; i++ {
		res[i] = make([]int, i+1)
		for j := 0; j <= i; j++ {
			if j == 0 || j == i {
				res[i][j] = 1
			} else {
				res[i][j] = res[i-1][j] + res[i-1][j-1]
			}
		}
	}
	return res[rowIndex]
}

//120. 三角形最小路径和
func minimumTotal(triangle [][]int) int {
	states := make([][]int, len(triangle))
	states[0] = make([]int, 1)
	states[0][0] = triangle[0][0]
	for i := 1; i < len(triangle); i++ {
		states[i] = make([]int, i+1)
		for j := 0; j <= i; j++ {
			if j == 0 {
				states[i][j] = states[i-1][j] + triangle[i][j]
			} else if j == i {
				states[i][j] = states[i-1][j-1] + triangle[i][j]
			} else {
				states[i][j] = min(states[i-1][j], states[i-1][j-1]) + triangle[i][j]
			}
		}
	}
	min := math.MaxInt8
	for i := 0; i < len(states[len(states)-1]); i++ {
		if min > states[len(states)-1][i] {
			min = states[len(states)-1][i]
		}
	}
	return min
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

//剑指 Offer 42. 连续子数组的最大和
func maxSubArrayDP(nums []int) int {
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	res := nums[0]
	for i := 1; i < len(nums); i++ {
		dp[i] = max(nums[i], dp[i-1]+nums[i])
		if dp[i] > res {
			res = dp[i]
		}
	}
	return res
}

func rob(nums []int) int {
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	if len(nums) == 2 {
		return max(nums[1], nums[0])
	}
	if len(nums) == 1 {
		return nums[0]
	}
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = nums[1]
	dp[2] = max(nums[1], nums[0]+nums[2])
	for i := 3; i < len(nums); i++ {
		dp[i] = max(dp[i-2]+nums[i], dp[i-3]+nums[i])
	}
	return max(dp[len(dp)-2], dp[len(dp)-1])
}

//322. 零钱兑换,动态规划！
func coinChange(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}
	dp := make([]int, amount+1)
	for j := 0; j < len(coins); j++ {
		if coins[j] <= amount {
			dp[coins[j]] = 1
		}
	}
	min := func(a, b int) int {
		if a > b {
			return b
		}
		return a
	}
	for i := 0; i <= amount; i++ {
		if dp[i] != 0 {
			for j := 0; j < len(coins); j++ {
				if i+coins[j] <= amount {
					if dp[i+coins[j]] == 0 {
						dp[i+coins[j]] = dp[i] + 1
					} else {
						dp[i+coins[j]] = min(dp[i+coins[j]], dp[i]+1)
					}
				}
			}
		}
	}
	if dp[amount] == 0 {
		return -1
	}
	return dp[amount]
}

type product struct {
	pos, neg int
}

//152. 乘积最大子数组
func maxProduct(nums []int) int {
	dp := make([]product, len(nums))
	if nums[0] > 0 {
		dp[0] = product{
			pos: nums[0],
			neg: 0,
		}
	} else {
		dp[0] = product{
			pos: 0,
			neg: nums[0],
		}
	}
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	ans := nums[0]
	for i := 1; i < len(nums); i++ {
		pos, neg := 0, 0
		if nums[i] > 0 {
			//i-1可能是0
			pos = max(nums[i]*dp[i-1].pos, nums[i])
			neg = nums[i] * dp[i-1].neg
		} else if nums[i] < 0 {
			pos = nums[i] * dp[i-1].neg
			//i-1可能是0
			neg = min(nums[i]*dp[i-1].pos, nums[i])
		} else {
			pos, neg = 0, 0
		}
		dp[i] = product{
			pos: pos,
			neg: neg,
		}
		ans = max(dp[i].pos, ans)
	}
	return ans
}

//44. 通配符匹配
func isMatch1(s string, p string) bool {
	var f func(si, pi int)
	ans := false
	visited := make([][]bool, len(s)+1)
	for i := range visited {
		visited[i] = make([]bool, len(p)+1)
	}
	f = func(si, pi int) {
		if si > len(s) {
			return
		}
		if ans || visited[si][pi] {
			return
		}
		if pi == len(p) {
			if si == len(s) {
				ans = true
			}
			return
		}
		visited[si][pi] = true
		if p[pi] == '*' { // *匹配任意个字符
			for k := 0; k <= len(s)-si; k++ {
				f(si+k, pi+1)
			}
		} else if p[pi] == '?' { // ?匹配0个或者1个字符
			//匹配1个
			f(si+1, pi+1)
		} else if si < len(s) && p[pi] == s[si] { // 纯字符匹配才行
			f(si+1, pi+1)
		}
	}
	f(0, 0)
	return ans
}

//139. 单词拆分
func wordBreak(s string, wordDict []string) bool {
	m := make(map[string]bool)
	for i := range wordDict {
		m[wordDict[i]] = true
	}
	dp := make([]bool, len(s))
	//初始化
	for i := 1; i <= len(s); i++ {
		if m[s[:i]] {
			dp[i-1] = true
		}
	}
	for i := 1; i < len(s); i++ {
		if dp[i-1] {
			for j := i + 1; j <= len(s); j++ {
				if m[s[i:j]] {
					dp[j-1] = true
				}
			}
		}
	}
	return dp[len(dp)-1]
}

//221. 最大正方形
func maximalSquare(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i := range dp {
		dp[i][0] = 1
	}
	for j := range dp[0] {
		dp[0][j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			up, left := 0, 0
			if i != 0 {
				up = dp[i-1][j]
			}
			if j != 0 {
				left = dp[i][j-1]
			}
			dp[i][j] = left + up
		}
	}
	return dp[m-1][n-1]
}
//309. 最佳买卖股票时机含冷冻期
func maxProfit2(prices []int) int {
	max:=func(a,b int)int{
		if a>b{
			return a
		}
		return b
	}
	n:=len(prices)
	dp:=make([][]int,3)
	//0持有，1没有且不冷却，2卖出的那天（后一天是冷却）
	for i:=0;i<3;i++{
		dp[i]=make([]int,n)
	}
	dp[0][0]=-prices[0]
	for i:=1;i<len(prices);i++{
		dp[0][i]=max(dp[0][i-1],dp[1][i-1]-prices[i])
		dp[1][i]=max(dp[1][i-1],dp[2][i-1])
		dp[2][i]=dp[0][i-1]+prices[i]
	}
	return max(dp[1][n-1],dp[2][n-1])
}

func countSubstrings(s string) int {
	ans:=len(s)
	for i:=range s{
		for j:=1;i-j>=0&&i+j<len(s);j++{
			if s[i-j]==s[i+j]{
				ans++
			}else {
				break
			}
		}
	}
	for i:=0.5;i<float64(len(s));i++{
		for j:=0.5;i-j>=0&&i+j<float64(len(s));j++{
			if s[int(i-j)]==s[int(i+j)]{
				ans++
			}else {
				break
			}
		}
	}
	return ans
}
//621. 任务调度器
func leastInterval(tasks []byte, n int) int {
	temp:=make([]int,26)
	for i:=range tasks{
		temp[tasks[i]-'A']++
	}
	sort.Ints(temp)
	i:=25
	for ;i>=1;i--{
		if temp[i]!=temp[i-1]{
			break
		}
	}
	max:=func(a,b int)int{
		if a>b{
			return a
		}
		return b
	}
	ans:=(temp[i]-1)*n+temp[i]+25-i
	return max(ans,len(tasks))
}
//312. 戳气球，动态规划
func maxCoins(nums []int) int {
	max:= func(a,b int)int {
		if a>b{
			return a
		}
		return b
	}
	n := len(nums)
	//状态转移方程
	rec := make([][]int, n + 2)
	for i := 0; i < n + 2; i++ {
		rec[i] = make([]int, n + 2)
	}
	//用于替代nums
	val := make([]int, n + 2)
	val[0], val[n+1] = 1, 1
	for i := 1; i <= n; i++ {
		val[i] = nums[i-1]
	}
	for i:=n-1;i>=0;i--{
		for j:=i+2;j<n+2;j++{
			for k:=i+1;k<j;k++{
				sum:=val[i]*val[k]*val[j]
				sum+=rec[i][k]+res[k][j]
				rec[i][j]=max(sum,rec[i][j])
			}
		}
	}
	return rec[0][n+1]
}
//238. 除自身以外数组的乘积
func productExceptSelf(nums []int) []int {
	n:=len(nums)
	ans,left,right:=make([]int,n),make([]int,n),make([]int,n)
	left[0]=1
	for i:=1;i<n;i++{
		left[i]=nums[i-1]*left[i-1]
	}
	right[n-1]=1
	for i:=n-2;i>=0;i--{
		right[i]=nums[i+1]*right[i+1]
	}
	for i:=range nums{
		ans[i]=left[i]*right[i]
	}
	return ans
}

